class Grammar
  def initialize(tokens)
    @index = 0
    @tokens = tokens

    # :declara[ors][nterm]
    @grammar = { 
               :programa         => [ [:declara, :rotina, /^begin$/, :sentencas, /^end$/] ] ,
               :declara          => [ [ :tipo_var, :variaveis, ';', :declara] , [:epson] ],
               :tipo_var         => [ [/^int$/,:id] ] ,
               :variaveis        => [ [:id, :mais_var] ] ,
               :mais_var         => [ [/^,$/, :variaveis] , [:epson] ],
               
               :rotina           => [ [:procedimento] , [:funcao] , [:epson] ] ,
               :procedimento     => [ [/^proc$/,  :id, :parametros, /^;$/, :declara, /^begin$/, :sentencas, /^end$/, :rotina] ],
               :parametros       => [ [/^\($/,  :lista_parametros, /^\)$/ ] , [:epson] ],
               :lista_parametros => [ [:lista_id, ':', :tipo_var, :cont_lista_par] ],
               :cont_lista_par   => [ [/^;$/, :lista_parametros] , [:epson] ],
               :lista_id         => [ [:id, :cont_lista_id] ],
               :cont_lista_id    => [ [/^,$/, :lista_id] , [:epson] ],
               :tipo_funcao      => [ [/^int$/] ],
               
               :sentencas        => [ [:comando, :mais_sentencas] ],
               :mais_sentencas   => [ [/^;$/, :cont_sentencas] ],
               :cont_sentencas   => [ [:sentencas] , [:epson] ],
               :var_read         => [ [:id, :mais_var_read] ],
               :mais_var_read    => [ [/^,$/,  :var_read] , [:epson] ],
               :var_write        => [ [:id, :mais_var_write] ],
               :mais_var_write   => [ [/^,$/, :var_write] , [:epson] ],
               :comando          => [ 
                                      [/^read$/, :var_read ] ,
                                      [/^write$/, :var_write] ,
                                      [/^to$/, :id, /^do$/, :sentencas, /^end$/] ,
                                      [/^do$/, :sentencas, /^until$/, :condicao] ,
                                      [/^while$/, :condicao, /^do$/, :sentencas] ,
                                      [/^if$/, :condicao, /^then$/, :sentencas, :pfalsa, /^fi$/] ,
                                      [:id, /^:=$/, :expressao],
                                      [:chamada_procedimento]
                                    ],

                :chamada_procedimento => [ [:id, :argumentos] ],
                :argumentos           => [ [/^\($/, :lista_arg, /^\)$/], [:epson] ],
                :lista_arg            => [ [:expressao, :cont_lista_arg] ],
                :cont_lista_arg       => [ [/^,$/, :lista_arg] , [:epson] ], 

                :condicao      => [ [:expressao, :relacao, :expressao] ],
                :pfalsa        => [ [/^else$/, :sentencas] , [:epson] ],
                :relacao       => [ [/^=$/,/^>$/,/^<$/,/^>=$/,/^<=$/,/^<>$/] ],
                :expressao     => [ [:termo, :outros_termos] ],
                :outros_termos => [ [:op_ad, :termo, :outros_termos], [:epson] ],
                :op_ad         => [ [/^(\+|-)$/] ],
                :termo         => [ [:fator, :mais_fatores] ],
                :mais_fatores  => [ [:op_mul, :fator, :mais_fatores], [:epson] ],
                :op_mul        => [ [/^(\*|\/)$/] ],

                :fator => [ [:id], [:intnum], [/^\($/,:expressao,/^\)$/], [:id, :argumentos] ],

                :id     => [ [/^[a-zA-Z]{1}[a-zA-Z0-9]*/] ],
                :intnum => [ [/^[0-9]+/] ]

              }


    find(@tokens.first)
    
  end
		      
	def backtrack
	end

  def find_next(token, pstack, nterm, stack)
    case nterm
      when Regexp 
        return true if token.token =~ nterm
      when Symbol
        find(token,[:id])
    end

    return false
  end

	def find(token, stack=[:programa])
    @grammar[stack.last].each_with_index do |ors,ors_id| #cada opcao de uma sentenca ->  x := a | b
      ors.each_with_index do |nterm,nterm_id| #cada nao terminal da sentenca  -> a,b

        case nterm
          when Symbol
            stack << nterm
            find(token,stack)

          when Regexp
            if token.token =~ nterm
              print stack.join(" -> ")
              print "\n"

              # parse o proximo token, se achar, esse eh valido
              next_term = @grammar[stack.last][ors_id][nterm_id+1]
              if next_term 
                if find_next(@tokens[@index+1],stack,next_term,[])
                  print "#{token.token} valido\n"
                else
                  print "Erro sintatico.\n"
                end
              else
                #Consumir stack afim de efetuar backtrack atras de validar o 
                #proximo token
              end

              exit
            else
              print "NAO ACHEI!"
              exit
            end
        end

      end
    end
	end
end

require 'compiler/token'
g = Grammar.new([Token.new('int',:reserved), Token.new('a',:identifier)])
